/*
提交链接：https://leetcode.cn/problems/number-of-islands/submissions/584132954/
200. 岛屿数量-中等
完成日期：2024/10/17
并查集
*/

class Solution {
public:
    static const int MAXN = 89997; // 最大可能的并查集大小
    int father[MAXN];              // 并查集父节点数组
    int cols;                         // 网格列数
    int sets;                         // 连通分量数目

    // 将二维索引 (a, b) 转化为一维索引
    int index(int a, int b) {
        return a * cols + b; // 使用行优先顺序
    }

    // 并查集的路径压缩 find 函数
    int find(int i) {
        if (i != father[i]) {
            father[i] = find(father[i]);
        }
        return father[i];
    }

    // 并查集的 union 函数，将两个集合合并
    void unionSets(int a, int b, int c, int d) {
        int fx = find(index(a, b));
        int fy = find(index(c, d));
        if (fx != fy) {
            father[fx] = fy;
            sets--;
        }
    }

    // 初始化并查集，计算初始岛屿数
    void build(int m, int n, vector<vector<char>>& grid) {
        cols = n;
        sets = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    int idx = index(i, j);
                    father[idx] = idx;
                    sets++;
                }
            }
        }
    }

    // 主函数，计算岛屿数量
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        build(m, n, grid);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    // 判断左侧和上方是否也是陆地，尝试合并
                    if (i > 0 && grid[i - 1][j] == '1') {
                        unionSets(i, j, i - 1, j);
                    }
                    if (j > 0 && grid[i][j - 1] == '1') {
                        unionSets(i, j, i, j - 1);
                    }
                }
            }
        }
        return sets;
    }
};